1. Field of the Invention
This invention relates to buffers used within data communications systems and more particularly to a self-adjusting elasticity buffer for processing packets or streams of data. A xe2x80x9cpacketxe2x80x9d or xe2x80x9cstreamxe2x80x9d, as used within context of this disclosure, is a collection of individual data units, such as 2-bit, 4-bit or 8-bit words, which form a contiguous group of data.
2. Description of Related Art
Data communication devices, such as shown in FIG. 1, often use elasticity buffers to re-synchronize a data stream from one clock domain to another. Within the receiver (RX), the data stream is written into an elasticity buffer in accordance with a receive clock signal (RX CLK), i e., write clock, in the form of original receive data (RX DATA), i. e., write data. The RX DATA is subsequently read out of the buffer in accordance with atransmit clock signal (TX CLK), i e., read clock. Thus when the read data is received by the transmitter it is synchronous with the transmit clock.
In a typical implementation, the elasticity buffer is implemented using a first-in first-out (FIFO) buffer that writes data words using a write clock and reads the data words using a separate read clock. With reference to FIG. 2, each of the words in the data stream is individually written into the buffer in individual cells beginning at 0, as indicated by the write pointer. Once data is written into the cell numbered N, data is read from the buffer beginning at cell 0, as indicated by the read pointer. The write pointer continues to write data to buffer cells N+1 through 2N as the read pointer continues to read data After writing data to the 2N cell the write pointer begins writing data to the 0 cell again, thus the buffer is circular in nature.
Ideally, when the read clock and write dock are operating at the same frequency, the read pointer lags the write pointer by N words through the entire write/read cycle. However, the read clock and write clock inputs to the elasticity buffer are often offset in frequency. The frequency offset causes relative movement between the read and write pointers which, overtime increases or decreases the gap between the two pointers depending on the frequencies of the write and read clocks. This relative movement of the read and write pointers is referred to as xe2x80x9cdrift.xe2x80x9d When data is being written to the buffer faster than it is being read, the write pointer drifts toward the read pointer and eventually passes the read pointer. This condition is referred to as an xe2x80x9coverrunxe2x80x9d because the write pointer writes data to a buffer cell which contains data which has not yet be read by the read pointer. When data is being read from the buffer faster than it is being written, the read pointer drifts toward the write pointer and eventually passes the write pointer. This condition is referred to as an xe2x80x9cunderrunxe2x80x9d because the read pointer reads data from a buffer which has not yet had data written to it by the write pointer. Either an overrun or underrun condition results in the corruption of data. The system typically includes a mechanism for detecting these conditions and providing an error signal.
Current designs of the elasticity buffer attempt to compensate for overrun and underrun conditions by sizing the elasticity buffer to accommodate for the maximum xe2x80x9cfrequency offsetxe2x80x9d between the write and read clocks. The frequency offset is relative to the data rate of the system and is defined by the following equation:                               freq          ⁢                      xe2x80x83                    ⁢          offset                =                              "LeftBracketingBar"                                          W                freq                            -                              R                freq                                      "RightBracketingBar"                                D            rate                                              (                  Eq          .                      xe2x80x83                    ⁢          1                )            
where:
Wfreq=frequency of the write clock
Rfreq=frequency of the read clock
Drate=data rate of the system
Accordingly, if the data rate of the system is 50 Mhz and the difference between the write clock and read clock frequencies is 10 kHz the frequency offset is 0.0002. This value is commonly expressed as 200 part-per-million (ppm).
In a standard elasticity buffer the FIFO size is at least 2N, where N is defined by the following equation:
N=freq offsetmaxxc3x97data lengthmaxxe2x80x83xe2x80x83(Eq. 2)
where:
freq offsetmax=the maximum frequency offset as determined using Eq. 1
data lengthmax=the maximum length of the data stream in words
For a maximum frequency offset of 200 ppm and a maximum data stream length of 40,000 words, N equals 8. Thus, the size of the standard elasticity buffer is 16. operation, the elasticity buffer is loaded halfway, to a xe2x80x9cpreload valuexe2x80x9d of N, before the reading of data begins. This allows the read pointer to drift N words in either direction without causing a loss of data by an overrun or underrun condition. This preloading, however, introduces an initial delay in the reading of date, this delay is referred to as a latency and is described further below.
Disadvantages associated with this implementation of the elasticity buffer include the FIFO size and latency. As mentioned above, the size of the buffer is at least 2N in order to accommodate the maximum possible drift between the read and write pointers. Latency is the amount of time between the writing of a word into the buffer and the reading of a word from the buffer. The latency between the data in and data out of the buffer are shown in FIGS. 3a through 3c. As shown in FIG. 3a, the latency at the start of the data stream is N, because N words are written before the read pointer starts reading. At the end of the data stream, the latency is between 0 and 2N words, depending on the relative frequencies of the write and read clocks. If the clocks are running at the same frequency the latency is N, as shown in FIG. 3a. If the read clock is running faster than the write clock the latency approaches zero, as shown in FIG. 3b, whereas if the write clock is running faster than the read dock the latency approaches 2N, as shown in FIG. 3c. As the latency approaches 2N the possibility of the present data stream interfering with a subsequent data stream increases.
Thus there exists a need in the art to provide a buffer of reduced size with reduced latency at the end of a data stream. The present invention fulfills these needs.
Briefly, and in general terms, the invention relates to methods of, and systems for, processing data through a buffer.
In one embodiment, the invention relates to a method of processing a plurality of data packets, each having a number of data units, through a buffer in accordance with a write clock and a read dock. The buffer has a plurality of sequentially numbered storage cells. The method includes the steps of selecting an initial preload value; writing the data units into the storage cells using a write pointer operating in accordance with the write clock; and when the storage cell of the buffer having the number equal to the preload value has been written to, reading data units from the storage cells using a read pointer operating in accordance with the read clock. The method further includes the steps of determining the relative frequencies of the write and read clocks; and for subsequent data packets, selectively adjusting the preload value to compensate for differences between the write frequency and the read frequency.
By adjusting the preload value to compensate for differences between the write frequency and the read frequency, the present invention prevents the over writing of data into a storage cell which contains data which has not yet been read and prevents the reading of storage cells which have not yet had data written to.
In an additional aspect of this embodiment the write pointer and read pointer each have a counter associated therewith and the step of determining the relative frequencies of the write and read clocks includes the step of, after the start of the reading of data by the read pointer and during the writing of data from the first data packet, comparing the value of the write-pointer counter with the value of the read-pointer counter. In a further aspect, the step of selectively adjusting the preload value comprises the steps of, if the read-pointer counter value is less than the write-pointer counter value by an amount greater than the initial preload value, setting the preload value to a low preload value having a value less than the initial preload value; and if the read-pointer counter value is less than the write-pointer counter value by an amount less than the initial preload value, setting the preload value to a high preload value having a value greater than the initial preload value. In another facet of this embodiment, the write pointer and read pointer each have a counter associated therewith and the step of determining the relative frequencies of the write and read clocks comprises the step of, at the end of the writing of the first data packet, counting the number of words read by the read pointer in order to empty the storage cells. In a further facet, the step of selectively adjusting the preload value comprises the steps of, if the number of words counted is greater than the initial preload value, setting the preload value to a low preload value having a value less than the initial preload value; and if the number of words counted is less than the initial preload value, setting the preload value to a high preload value having a value greater than the initial preload value. In yet another aspect of this embodiment, the write clock and the read clock each have a frequency counter associated therewith and the step of determining the relative frequencies of the write and read clocks comprises the steps of, counting the cycles of the write clock during a fixed period of time; and counting the cycles of the read clock during the same fixed period of time. In a further aspect, the step of adjusting the preload value comprises the steps of, if the write clock frequency is greater than the read clock frequency, setting the preload value to a low preload value having a value less than the initial preload value; and if the write clock frequency is less than the read clock frequency, setting the preload value to a high preload value having a value greater than the initial preload value.
In another embodiment, the invention relates to a method of compensating for the drift between a write pointer and a read pointer processing packets of data having a number of data units through a FIFO buffer. The write and read pointers operate in accordance with a write and read clock respectively. The method includes the steps of sizing the FIFO buffer to include a number of storage cells equal to the product of the maximum frequency offset between the write clock and read clock and the maximum number of data units in a packet; delaying the start of the read pointer, relative to the write pointer, by a portion of the number of storage cells in the FIFO; and determining if the read pointer is drifting toward or away from the write pointer. The method further includes the steps of, if the read pointer is drifting away from the write pointer, for subsequent data packets, starting the read pointer almost immediately after the write pointer writes to the first storage cell in the FIFO; and if the read pointer is drifting toward the write pointer, for subsequent data packets, starting the read pointer almost immediately prior to the time at which the write pointer writes to the last storage cell in the FIFO.
By sizing the FIFO buffer to include a number of storage cells equal to the product of the maximum frequency offset between the write clock and read clock and the maximum number of data units in a packet and by adjusting the starting of the read pointer based on the drift of the read pointer, the maximum latency at the end of the data stream is reduced compared to the latency associated with a standard FIFO buffer. Furthermore, the FIFO size is reduced compared to a standard FIFO buffer, thus reducing the overall cost of the system.
In an additional facet of this embodiment, the write pointer and read pointer each have a counter associated therewith and the step of determining if the read pointer is drifting toward or away from the write pointer comprises the steps of, after the start of the reading of data by the read pointer and during the writing of data from the first data packet, comparing the value of the write-pointer counter to the value of the read-pointer counter; if the read-pointer counter value is less than the write-pointer counter value by an amount greater than the number of storage cells which the start of the read pointer was delayed, indicating that the read pointer is drifting away from the write pointer; and if the read-pointer counter value is less than the write-pointer counter value by an amount less than the number of storage cells which the start of the read pointer was delayed, indicating that the read pointer is drifting toward the write pointer. In another facet, the write pointer and read pointer each have a counter associated therewith and the step of determining if the read pointer is drifting toward or away from the write pointer comprises the steps of, at the end of the writing of the first data packet, counting the number of words read by the read pointer in order to empty the FIFO storage cells; if the number of words counted is greater than the number of storage cells which the start of the read pointer was delayed, indicating that the read pointer is drifting away from the write pointer; and if the number of words counted is less than the number of storage cells which the start of the read pointer was delayed, indicating that the read pointer is drifting toward the write pointer. In yet another aspect, the write clock and the read clock each have a frequency counter associated therewith and the step of determining if the read pointer is drifting toward or away from the write pointer comprises the steps of, counting the cycles of the write clock during a fixed period of time and counting the cycles of the read clock during the same fixed period of time. The step further includes the steps of, if the write clock frequency is greater than the read clock frequency, indicating that the read pointer is drifting away from the write pointer; and if the write clock frequency is less than the read clock frequency, indicating that the read pointer is drifting toward the write pointer.
In another embodiment, the invention relates to a method of processing a plurality of data packets, each having a number of data units, through a buffer in accordance with a write clock and a read clock. The buffer has a plurality of sequentially numbered storage cells. The method includes the steps of writing data to the storage cells in accordance with the write clock frequency; reading data from the storage cells in accordance with the read clock frequency; and adjusting the time at which data is begun to be read relative to the time at which data is begun to be written to prevent the over writing of data into a storage cell which contains data which has not yet been read and to prevent the reading of storage cells which have not yet had data written to.
In another embodiment, the invention relates to a system for processing packets of data having a number of data units. The system includes a read clock having an operating frequency; a write clock having an operating frequency; and a FIFO having a number of storage cells substantially equal to the product of the maximum frequency offset and the maximum number of data units in the data packets. The system further includes a write pointer for writing data to the storage cells in accordance with the write clock frequency; a read pointer for reading data from the storage cells in accordance with the read clock frequency; and a state machine for controlling the time at which the read pointer starts reading data.
In an additional facet of this embodiment, the state machine includes means for delaying the start of the read pointer relative to the write pointer by a default preload value equal to a portion of the total number of storage cells in the FIFO and means for calculating the relative positions of the write pointer and read pointer. The state machine further includes means for selectively adjusting the preload value depending on the relative positions of the write pointer and read pointer. In a further aspect, the calculating means includes a write-pointer counter for counting the number of storage cells written to by the write pointer; a read-pointer counter for counting the number of storage cells read by the read pointer; and means for comparing the values of the read-pointer counter and the write-pointer counter after the start of the reading of data by the read pointer and during the writing of data from the first data packet. In a further aspect, the adjusting means includes means for setting the preload value to a low preload value having a value less than the initial preload value if the read-pointer counter value is less than the write-pointer counter value by an amount greater than the initial preload value; and means for setting the preload value to a high preload value having a value greater than the initial preload value if the read-pointer counter value is less than the write-pointer counter value by an amount less than the initial preload value. In other facets of this embodiment, the calculating means includes a read-pointer counter for counting the number of words read by the read pointer in order to empty the FIFO storage cells after the end of the writing of a data packet and the adjusting means includes means for setting the preload value to a low preload value having a value less than the initial preload value if the number of words counted is greater than the initial preload value; and means for setting the preload value to a high preload value having a value greater than the initial preload value if the number of words counted is less than the initial preload value. In other facets of this embodiment, the calculating means includes a write-clock frequency counter for determining the frequency of the write clock; a read-clock frequency counter for determining the frequency of the read clock; and a device for comparing the write-clock frequency and the read-clock frequency and producing as output, the difference between the two and the adjusting means includes means for setting the preload value to a low preload value having a value less than the initial preload value when the write clock frequency is greater than the read clock frequency; and means for setting the preload value to a high preload value having a value greater than the initial preload value when the write clock frequency is less than the read clock frequency.
In another embodiment, the invention relates to a buffer for allowing the influx and outflow of a number of data units forming a data stream. The buffer is for use in a system having a write clock and a read clock and includes a write pointer for writing data in accordance with the frequency of the write clock and a read pointer for reading data in accordance with the frequency of the read clock. The buffer further includes a number of storage cells substantially equal to the product of the maximum frequency offset between the write and read clocks and the maximum number of data units in the data stream, the storage cells responsive to the write pointer for receiving data units and the read pointer for providing data units.